package advanced.class05;

/**
 * 求数组的最大亦或和————前缀树求解（讲过——第六课）
 *
 * 亦或运算： 亦或运算满足交换律和结合率
 * a ^ b = c
 * a = b ^ c
 * a = c ^ b
 *
 */
public class Code_05_Max_EOR {

	//----------解法一：最暴力的解法----------
	public static int maxXor1(int[] arr){
		int res = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			int xor = 0;
			for (int j = i; j < arr.length; j++) {
				xor ^= arr[j];
				res = Math.max(res,xor);
			}
		}
		return res;
	}

	// --------------解法二：使用dp数组做简单优化-----------------
	public static int maxXor2(int[] arr){
		int max = Integer.MIN_VALUE;
		int[] dp = new int[arr.length];
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
			for (int start = 1; start <= i; start++) {
				int startToIZxor = eor ^ dp[start - 1];
				max = Math.max(max,startToIZxor);
			}
			dp[i] = eor;
			max = Math.max(max,dp[i]);
		}
		return max;
	}


	//-------------方法三： 前缀树求解---------------
	// 节点类，存储int值得二进制元素
	public static class Node {
		// 书中只有一个属性，长度为2的Node数组,分别表示0,1
		public Node[] nexts = new Node[2];   //0 , 1
	}

	// 前缀树结构
	public static class NumTrie {
		public Node head = new Node();

		// 将每个int型数据加入前缀树
		public void add(int num) {
			Node cur = head;
			for (int move = 31; move >= 0; move--) {
				int path = ((num >> move) & 1);  // 按位找出当前位置上面得元素（0或1）（0&1为0， 1&1为1）
				cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];  // 当前位置上得path如果为空，那么就建出来，否则，直接转移到下一层
				cur = cur.nexts[path];
			}
		}

		// num.从0-i的亦或结果中选出最优的亦或和结果返回
		public int maxXor(int num) {
			Node cur = head; // 从头节点开始
			int res = 0;
			for (int move = 31; move >= 0; move--) {
				int path = (num >> move) & 1;  // 首先还是确定出当前位置是0或者1
				int best = move == 31 ? path : (path ^ 1);  // 如果是最高位符号位，我们希望可以和path保持同号，因为这样才可以保证符号位为0
				best = cur.nexts[best] != null ? best : (best ^ 1); // 如果当前节点的best没有被开发过，那么不走这条路，转而走另外一条路
				res |= (path ^ best) << move;    // 计算亦或结果，当前位置亦或之后，左移32位，然后再与之前的计算的res相或，计算结果。
				cur = cur.nexts[best];         // cur节点移往下一位
			}
			return res;
		}
	}

	public static int maxXorSubarray(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		int eor = 0;
		NumTrie numTrie = new NumTrie();  // 创建前缀树
		numTrie.add(0);          // 将初始值0扔进去
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
			// 这部是关键，假设现在eor是数组元素0-7位置的疑惑和，纳闷当前数组的最大亦或和为从前缀树种挑选一个树与当前eor亦或结果最大的值即为最终的max
			// 因为亦或满足交换律和结合率（ a = b ^ c）, 那么（c = a ^ b = b ^ a）
			max = Math.max(max, numTrie.maxXor(eor));
			numTrie.add(eor);
		}
		return max;
	}

	// for test
	public static int comparator(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			int eor = 0;
			for (int j = i; j < arr.length; j++) {
				eor ^= arr[j];
				max = Math.max(max, eor);
			}
		}
		return max;
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 30;
		int maxValue = 50;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr = generateRandomArray(maxSize, maxValue);
			int res = maxXor2(arr);
			int comp = comparator(arr);
			if (res != comp) {
				succeed = false;
				printArray(arr);
				System.out.println(res);
				System.out.println(comp);
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}
}
